|
ハッシュ関数などについて衝突(collision)とは、2つの異なるデータからハッシュ関数などで生成したハッシュ値など（チェックサム・フィンガープリント・メッセージダイジェストなど）の値が同じ値になることである。 ほとんどの分野において衝突は一般に望ましくない結果ではあるが、その「望ましくなさ」はその応用の目的によって異なる。また鳩の巣原理により、ある集合全体からその集合より小さい集合への写像では必ず衝突が発生するが、メッセージダイジェストなどではその確率が十分に低いかどうかが問題となる。 相同DNA配列や、ほぼ同じ内容の音声ファイルなど、よく似たデータを同一視するためにハッシュ関数とフィンガープリントを使用する場合、ハッシュ関数は似たデータに対して似た結果を出し、あるいは衝突を発生する（確率ができる限り大きくなる）ように設計される。これは一般と逆に必要な場合には衝突が望まれる例である。 ビットの化けや抜けや混入をチェックするチェックサムなどはよく似た入力に対して、可能であれば十分に異なるハッシュ値を生成することが望まれ、衝突を発生させる確率ができる限り小さくなるように設計される。一方で全く異なるデータ間での衝突については通常は意識されない。こういった誤り検出訂正の類はハッシュとは別とすることもある。 ハッシュテーブルにおいて、衝突はルックアップ処理のコストを増加させる。こういった応用には関数の計算量と結果の品質のどちらを重視するか等のトレードオフもある。 プロキシサーバやファイルのバックアップシステムにおいて不要なファイルの保存や転送を省略するためにはフィンガープリントが使用されるが、ここでの衝突は、単に本来ならば必要なかったはずの転送が必要になったというような結果であれば問題ないが、場合によっては不適切な処理やデータ消失の原因になりうる。 暗号分野の応用では衝突が致命的なものもあり、暗号学的ハッシュ関数と呼ばれる特別な一分野としてさかんに研究されている。この分野ではハッシュ関数について「弱衝突耐性」「強衝突耐性」といった術語が定義されており、暗号学的ハッシュ関数はこれらについて、目的に応じて必要な強度を満たしていることが求められる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ハッシュ関数などについて衝突(collision)とは、2つの異なるデータからハッシュ関数などで生成したハッシュ値など（チェックサム・フィンガープリント・メッセージダイジェストなど）の値が同じ値になることである。ほとんどの分野において衝突は一般に望ましくない結果ではあるが、その「望ましくなさ」はその応用の目的によって異なる。また鳩の巣原理により、ある集合全体からその集合より小さい集合への写像では必ず衝突が発生するが、メッセージダイジェストなどではその確率が十分に低いかどうかが問題となる。相同DNA配列や、ほぼ同じ内容の音声ファイルなど、よく似たデータを同一視するためにハッシュ関数とフィンガープリントを使用する場合、ハッシュ関数は似たデータに対して似た結果を出し、あるいは衝突を発生する（確率ができる限り大きくなる）ように設計される。これは一般と逆に必要な場合には衝突が望まれる例である。ビットの化けや抜けや混入をチェックするチェックサムなどはよく似た入力に対して、可能であれば十分に異なるハッシュ値を生成することが望まれ、衝突を発生させる確率ができる限り小さくなるように設計される。一方で全く異なるデータ間での衝突については通常は意識されない。こういった誤り検出訂正の類はハッシュとは別とすることもある。ハッシュテーブルにおいて、衝突はルックアップ処理のコストを増加させる。こういった応用には関数の計算量と結果の品質のどちらを重視するか等のトレードオフもある。プロキシサーバやファイルのバックアップシステムにおいて不要なファイルの保存や転送を省略するためにはフィンガープリントが使用されるが、ここでの衝突は、単に本来ならば必要なかったはずの転送が必要になったというような結果であれば問題ないが、場合によっては不適切な処理やデータ消失の原因になりうる。暗号分野の応用では衝突が致命的なものもあり、暗号学的ハッシュ関数と呼ばれる特別な一分野としてさかんに研究されている。この分野ではハッシュ関数について「弱衝突耐性」「強衝突耐性」といった術語が定義されており、暗号学的ハッシュ関数はこれらについて、目的に応じて必要な強度を満たしていることが求められる。」の詳細全文を読む スポンサード リンク
|